import java.util.Arrays;

public class SimpleSort {
    public static void main(String[] args) {
        int[] array={2,3,4,5,6,9,8,5,54,3,5,6,3,4,5};
        // new SimpleSort().bubbleSort(array);
        // new SimpleSort().selectionSort(array);
        new SimpleSort().shellSort(array);

        System.out.println(Arrays.toString(array));
    }

    void bubbleSort(int[] array){
        for(int i=0;i<array.length;i++){
            //再减1是为了避免j+1越界
            for(int j=0;j<array.length-i-1;j++){
                if(array[j]>array[j+1]){
                    swap(array, j+1, j);
                }
            }
        }
    }

    void selectionSort(int [] array){
        // for(int i=0;i<array.length;i++){
        //     int min=i; // 标记最小值的位置
        //     for(int j=i+1;j<array.length;j++){
        //         if(array[j]<array[min]){
        //             min=j;
        //         }
        //     }
        //     swap(array,i,min);
        // }
        for(int i=0;i<array.length;i++){
            int max=0; // 标记最大值位置
            for(int j=0;j<array.length-i;j++){
                if(array[j]>array[max]){
                    max=j;
                }
            }
            swap(array, array.length-i-1, max);
        }
    }

    //间隔为1的希尔排序
    void insertionSort(int[] array){
        //遍历无序部分
        for(int i=1;i<array.length;i++){
            //存储第一个无序值
            int value=array[i];
            int j =i-1;
            while(j>=0 && value<array[j]){
                array[j+1]=array[j];
                j--;
            }
            array[j+1]=value;
        }

    }

    //插入排序的改良
    //间隔可以不为1
    void shellSort(int[] array){
        for(int gap=array.length/2;gap>0;gap/=2){
            //首次，每组第一个元素视为有序，从第二个元素开始
            for(int i=gap;i<array.length;i++){
                //存储第一个无序值
                int value=array[i];
                //遍历有序部分，插入该无序值
                int j=i-gap;
                while(j>=0 && value<array[j]){
                    //插入引起的元素后移
                    array[j+gap]=array[j];
                    j-=gap;
                }
                array[j+gap]=value;
            }
        }
        
    }

    void swap(int[] array,int i,int j){
        int temp=array[i];
        array[i]=array[j];
        array[j]=temp;
    }
}
